package leetcode;

import java.util.HashMap;

/**
 * @Classname MaxProfit
 * @Author happytaohaha
 * @Date 2020/3/2
 * @Description 买卖股票的最佳时机III
 * <p>
 * 动态规划dp
 */
public class MaxProfit_0123 {
    public static int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int K = 2;
        int[][] dp = new int[prices.length][K + 1];
        for (int k = 1; k <= K; k++) {
            for (int i = 1; i < prices.length; i++) {
                int min = Integer.MAX_VALUE;
                //找出第 0 天到第 i-1 天 prices[buy] - dp[buy][k - 1] 的最小值
                for (int buy = 0; buy < i; buy++) {
                    min = Math.min(prices[buy] - dp[buy][k - 1], min);
                }
                //比较不操作和选择一天买入的哪个值更大
                    dp[i][k] = Math.max(dp[i - 1][k], prices[i] - min);
            }
        }
        return dp[prices.length - 1][K];
    }

    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{1,2,3,4,5}));
    }
}
